{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<link href='https://fonts.googleapis.com/css?family=Passion+One' rel='stylesheet' type='text/css'><style>div.attn { font-family: 'Helvetica Neue'; font-size: 30px; line-height: 40px; color: #FFFFFF; text-align: center; margin: 30px 0; border-width: 10px 0; border-style: solid; border-color: #5AAAAA; padding: 30px 0; background-color: #DDDDFF; }hr { border: 0; background-color: #ffffff; border-top: 1px solid black; }hr.major { border-top: 10px solid #5AAA5A; }hr.minor { border: none; background-color: #ffffff; border-top: 5px dotted #CC3333; }div.bubble { width: 65%; padding: 20px; background: #DDDDDD; border-radius: 15px; margin: 0 auto; font-style: italic; color: #f00; }em { color: #AAA; }div.c1{visibility:hidden;margin:0;height:0;}div.note{color:red;}</style>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#  Ebnable HTML/CSS \n",
    "from IPython.core.display import HTML\n",
    "HTML(\"<link href='https://fonts.googleapis.com/css?family=Passion+One' rel='stylesheet' type='text/css'><style>div.attn { font-family: 'Helvetica Neue'; font-size: 30px; line-height: 40px; color: #FFFFFF; text-align: center; margin: 30px 0; border-width: 10px 0; border-style: solid; border-color: #5AAAAA; padding: 30px 0; background-color: #DDDDFF; }hr { border: 0; background-color: #ffffff; border-top: 1px solid black; }hr.major { border-top: 10px solid #5AAA5A; }hr.minor { border: none; background-color: #ffffff; border-top: 5px dotted #CC3333; }div.bubble { width: 65%; padding: 20px; background: #DDDDDD; border-radius: 15px; margin: 0 auto; font-style: italic; color: #f00; }em { color: #AAA; }div.c1{visibility:hidden;margin:0;height:0;}div.note{color:red;}</style>\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "___\n",
    "Enter Team Member Names here (double click to edit):\n",
    "\n",
    "- Name 1:\n",
    "- Name 2:\n",
    "- Name 3:\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "________\n",
    "<a id=\"top\"></a>\n",
    "# Live Session Assignment Two\n",
    "In the following assignment you will be asked to fill in python code and derivations for a number of different problems. Please read all instructions carefully and turn in the rendered notebook (.ipynb file, remember to save it!!) or HTML of the rendered notebook before the end of class.\n",
    "\n",
    "## Contents\n",
    "* <a href=\"#Loading\">Loading the Classification Data</a>\n",
    "* <a href=\"#using_trees\">Using Decision Trees - Gini</a>\n",
    "\n",
    "**These contents will become available during the live session: **\n",
    "* <a href=\"#entropy\">Using Decision Trees - Entropy</a>\n",
    "* <a href=\"#multi\">Multi-way Splits</a>\n",
    "* <a href=\"#sklearn\">Decision Trees in Scikit-Learn</a>\n",
    "\n",
    "________________________________________________________________________________________________________\n",
    "<a id=\"Loading\"></a>\n",
    "<a href=\"#top\">Back to Top</a>\n",
    "## Loading the Classification Data\n",
    "Please run the following code to read in the \"digits\" dataset from sklearn's data loading module. This is identical to the first in class assignment for loading the data into matrices. `ds.data` is a matrix of feature values and `ds.target` is a column vector of the class output (in our case, the hand written digit we want to classify). Each class is a number (0 through 9) that we want to classify as one of ten hand written digits. \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "features shape: (1797, 64)\n",
      "target shape: (1797,)\n",
      "range of target: 0 9\n"
     ]
    }
   ],
   "source": [
    "from sklearn.datasets import load_digits\n",
    "import numpy as np\n",
    "from __future__ import print_function\n",
    "\n",
    "ds = load_digits()\n",
    "\n",
    "# this holds the continuous feature data\n",
    "print('features shape:', ds.data.shape) # there are 1797 instances and 64 features per instance\n",
    "print('target shape:', ds.target.shape )\n",
    "print('range of target:', np.min(ds.target),np.max(ds.target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "________________________________________________________________________________________________________\n",
    "<a id=\"using_trees\"></a>\n",
    "<a href=\"#top\">Back to Top</a>\n",
    "## Using Decision Trees\n",
    "In the videos, we talked about the splitting conditions for different attributes. Specifically, we discussed the number of ways in which it is possible to split a node, depending on the attribute types. To understand the possible splits, we need to understand the attributes. For the question below, you might find the description in the `ds['DESCR']` field to be useful. You can see the field using `print(ds['DESCR'])`\n",
    "\n",
    "**Question 1:** For the digits dataset, what are the type(s) of the attributes? How many attributes are there? What do they represent?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "## Enter your comments here\n",
    "\n",
    "\n",
    "\n",
    "## Enter comments here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "## Using the gini coefficient\n",
    "We talked about the gini index in the videos.  The gini coefficient for a **given split** is given by:\n",
    "$$Gini=\\sum_{t=1}^T \\frac{n_t}{N}gini(t)$$\n",
    "where $T$ is the total number of splits (2 for binary attributes), $n_t$ is the number of instances in node $t$ after splitting, and $N$ is the total number of instances in the parent node. $gini(t)$ is the **gini index for each individual node that is created by the split** and is given by:\n",
    "$$gini(t)=1-\\sum_{j=0}^{C-1} p(j|t)^2$$\n",
    "where $C$ is the total number of possible classes and $p(j|t)$ is the probability of class $j$ in node $t$ (i.e., $n_j==$ the count of instances belonging to class $j$ in node $t$, normalized by the total number of instances in node $t$).\n",
    "$$ p(j|t) = \\frac{n_j}{n_t}$$ \n",
    "\n",
    "For the given dataset, $gini(t)$ has been programmed for you in the function `gini_index`. \n",
    "\n",
    "* `def gini_index(classes_in_split):`\n",
    " * To use the function, pass in a `numpy` array of the class labels for a node as (i.e., pass in the rows from `ds.target` that make up a node in the tree) and the gini will be returned for that node. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# compute the gini of several examples for the starting dataset\n",
    "# This function \"gini_index\" is written for you. Once you run this block, you \n",
    "#   will have access to the function for the notebook. You do not need to know \n",
    "#   how this function works--only what it returns \n",
    "# This function returns the gini index for an array of classes in a node.\n",
    "def gini_index(classes_in_split):\n",
    "    # pay no attention to this code in the function-- it just computes the gini for a given split \n",
    "    classes_in_split = np.reshape(classes_in_split,(len(classes_in_split),-1))\n",
    "    unique_classes = np.unique(classes_in_split)\n",
    "    gini = 1\n",
    "    for c in unique_classes:\n",
    "        gini -= (np.sum(classes_in_split==c) / float(len(classes_in_split)))**2\n",
    "        \n",
    "    return gini"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the example below, the function is used calculate the gini for splitting the dataset on feature 28, with value 2.5. In this example, we need to create two separate tree nodes: the first node has all the `ds.target` labels when feature 28 is greater than 2.5, the second node has all the rows from `ds.target` where feature 28 is less than 2.5. The steps are outlined below. **Read this carefully to understand what the code does below in the block following this.**\n",
    "- Feature 28 is saved into a separate variable `feature28 = ds.data[:,28]`\n",
    "- First all the target classes for the first node are calculated using `numpy` indexing `ds.target[feature28>2.5]` \n",
    " - Note: this grabs all the rows in `ds.target` (the classes) which have feature 28 greater than 2.5 (similar to indexing in pandas)\n",
    "- Second, those classes are passed into the function to get the gini for the right node in this split (i.e., feature 28 being greater than the threshold 2.5). \n",
    " - `gini_r = gini_index(ds.target[feature28>2.5])`\n",
    "- Third, the gini is calculated for the left node in the tree. This grabs only the rows in `ds.target` where feature 28 is less than 2.5.\n",
    "     - `gini_l = gini_index(ds.target[feature28<=2.5])`\n",
    "- Combining the gini indices is left as an exercise in the next section"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gini for right node of split: 0.884585786767\n",
      "gini for left node of split: 0.711540756654\n"
     ]
    }
   ],
   "source": [
    "#==========================Use the gini_index Example===============\n",
    "# get the value for this feature as a column vector \n",
    "# (this is like grabbing one column of the record table)\n",
    "feature28 = ds.data[:,28]\n",
    "\n",
    "# if we split on the value of 2.5, then this is the gini for each resulting node:\n",
    "gini_gr = gini_index(ds.target[feature28>2.5]) # just like in pandas, we are sending in the rows where feature28>2.5\n",
    "gini_lte = gini_index(ds.target[feature28<=2.5]) # and sending the rows where feature28<=2.5\n",
    "\n",
    "# compute gini example. This splits on attribute '28' with a value of 2.5\n",
    "print('gini for right node of split:', gini_gr)\n",
    "print('gini for left node of split:', gini_lte)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question 2:** Now, using the above values `gini_r` and `gini_l`. Calculate the combined Gini for the entire split. You will need to write the weighted summation (based upon the number of instances inside each node). To count the number of instances greater than a value using numpy, you can use broadcasting, which is a special way of indexing into a numpy array. For example, the code `some_array>5` will return a new numpy array of true/false elements. It is the same size as `some_array` and is marked true where the array is greater than `5`, and false otherwise. By taking the `sum` of this array, we can count how many times `some_array` is greater than `5`. \n",
    "\n",
    "`counts = sum(some_array>5)` \n",
    " \n",
    "You will need to use this syntax to count the values in each node as a result of splitting.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The total gini of the split for a threshold of 2.5 is: ??\n"
     ]
    }
   ],
   "source": [
    "## Enter your code here\n",
    "\n",
    "\n",
    "## Enter your code here\n",
    "print('The total gini of the split for a threshold of 2.5 is:',\"??\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:MLEnv]",
   "language": "python",
   "name": "conda-env-MLEnv-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
